package BinarySearch;

/*
找出第 k 小的距离对
数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

示例 1：
输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。
示例 2：
输入：nums = [1,1,1], k = 2
输出：0
示例 3：
输入：nums = [1,6,1], k = 3
输出：5

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/binary-search/xekymd/
 */

import java.util.Arrays;

public class _83找出第k小的距离对 {
    public static void main(String[] args) {

    }

    //官解： 排序 + 二分查找
    //尽管题目要求 i < j ,但是数对距离是绝对值，所以可以进行排序，排序不影响结果
    //O(nlogn×logD)   排序O(logn)
    class Solution {
        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
            while (left <= right) {
                int mid = (left + right) / 2;
                int cnt = 0;
                //给定距离 mid，计算所有距离小于等于 mid 的数对数目 cnt 可以使用二分查找：
                //枚举所有数对的右端点 j，二分查找大于等于 nums[j]−mid 的最小值的下标 i，
                //那么右端点为 j 且距离小于等于 mid 的数对数目为 j−i，计算这些数目之和。
                for (int j = 0; j < n; j++) {
                    int i = binarySearch(nums, j, nums[j] - mid);
                    cnt += j - i;
                }
                if (cnt >= k) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }

        public int binarySearch(int[] nums, int end, int target) {
            int left = 0, right = end;
            while (left < right) {
                int mid = (left + right) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return left;
        }
    }

    //官解： 排序 + 二分查找 + 双指针
    //O(n×(logn+logD))   排序O(logn)
    class Solution2 {
        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
            while (left <= right) {
                int mid = (left + right) / 2;
                int cnt = 0;
                for (int i = 0, j = 0; j < n; j++) {
                    //类似滑动窗口
                    while (nums[j] - nums[i] > mid) {
                        i++;
                    }
                    cnt += j - i;
                }
                if (cnt >= k) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    }


}
